import java.util.*;

public class Solution126 {

    static class Pair {
        String s;
        int step;
        int last;

        public Pair(String s, int step, int last) {
            this.s = s;
            this.step = step;
            this.last = last;
        }
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : wordList) {
            map.put(s, Integer.MAX_VALUE);
        }
        List<List<String>> ans=new ArrayList<>();
        if (!map.containsKey(endWord)) {
            return ans;
        }
        List<Pair> waiting=new ArrayList<>();
        map.put(beginWord, 1);
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(beginWord, 1, -1));
        int target=-1;
        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            if (pair.step==target){
                break;
            }
            waiting.add(pair);
            for (int i = 0; i < pair.s.length(); i++) {
                StringBuilder stringBuilder = new StringBuilder(pair.s);
                for (int j = 0; j < 26; j++) {
                    stringBuilder.setCharAt(i, (char) (j + 'a'));
                    if (stringBuilder.toString().equals(endWord)){
                        target=pair.step+1;
                        List<String> make=new ArrayList<>();
                        Pair pre=waiting.get(waiting.size()-1);
                        while (pre.last!=-1){
                            make.add(0,pre.s);
                            pre=waiting.get(pre.last);
                        }
                        make.add(endWord);
                        make.add(0,beginWord);
                        ans.add(make);
                    }else {
                        if (map.getOrDefault(stringBuilder.toString(), 0) == Integer.MAX_VALUE || map.getOrDefault(stringBuilder.toString(),0)==pair.step+1) {
                            map.put(stringBuilder.toString(), pair.step + 1);
                            queue.offer(new Pair(stringBuilder.toString(), pair.step + 1, waiting.size() - 1));
                        }
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution126().findLadders("red","tax",Arrays.asList("ted","tex","red","tax","tad","den","rex","pee")));
    }
}
